Spectral radius

 ( Spectral Theory ) 

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues.

More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by $\backslash rho(\backslash cdot)$.

---

Definition

---

Matrices Let be the eigenvalues of a matrix . The spectral radius of is defined as

$\backslash rho(A)\; =\; \backslash max\; \backslash left\; \backslash \{\; |\backslash lambda\_1|,\; \backslash dotsc,\; |\backslash lambda\_n|\; \backslash right\; \backslash \}.$

The spectral radius can be thought of as an infimum of all norms of a matrix. Indeed, on the one hand, $\backslash rho(A)\; \backslash leqslant\; \backslash |A\backslash |$ for every natural matrix norm $\backslash |\backslash cdot\backslash |$; and on the other hand, Gelfand's formula states that $\backslash rho(A)\; =\; \backslash lim\_\{k\backslash to\backslash infty\}\; \backslash |A^k\backslash |^\{1/k\}$. Both of these results are shown below.

However, the spectral radius does not necessarily satisfy $\backslash |A\backslash mathbf\{v\}\backslash |\; \backslash leqslant\; \backslash rho(A)\; \backslash |\backslash mathbf\{v\}\backslash |$ for arbitrary vectors $\backslash mathbf\{v\}\; \backslash in\; \backslash mathbb\{C\}^n$. To see why, let $r\; >\; 1$ be arbitrary and consider the matrix

.

The characteristic polynomial of $C\_r$ is $\backslash lambda^2\; -\; 1$, so its eigenvalues are $\backslash \{-1,\; 1\backslash \}$ and thus $\backslash rho(C\_r)\; =\; 1$. However, $C\_r\; \backslash mathbf\{e\}\_1\; =\; r\; \backslash mathbf\{e\}\_2$. As a result,

$\backslash |\; C\_r\; \backslash mathbf\{e\}\_1\; \backslash |\; =\; r\; >\; 1\; =\; \backslash rho(C\_r)\; \backslash |\backslash mathbf\{e\}\_1\backslash |.$

As an illustration of Gelfand's formula, note that $\backslash |C\_r^k\backslash |^\{1/k\}\; \backslash to\; 1$ as $k\; \backslash to\; \backslash infty$, since $C\_r^k\; =\; I$ if $k$ is even and $C\_r^k\; =\; C\_r$ if $k$ is odd.

A special case in which $\backslash |A\backslash mathbf\{v\}\backslash |\; \backslash leqslant\; \backslash rho(A)\; \backslash |\backslash mathbf\{v\}\backslash |$ for all $\backslash mathbf\{v\}\; \backslash in\; \backslash mathbb\{C\}^n$ is when $A$ is a Hermitian matrix and $\backslash |\backslash cdot\backslash |$ is the Euclidean norm. This is because any Hermitian Matrix is diagonalizable by a unitary matrix, and unitary matrices preserve vector length. As a result,

$\backslash |A\backslash mathbf\{v\}\backslash |\; =\; \backslash |U^*DU\backslash mathbf\{v\}\backslash |\; =\; \backslash |DU\backslash mathbf\{v\}\backslash |\; \backslash leqslant\; \backslash rho(A)\; \backslash |U\backslash mathbf\{v\}\backslash |\; =\; \backslash rho(A)\; \backslash |\backslash mathbf\{v\}\backslash |\; .$

---

Bounded linear operators In the context of a bounded linear operator on a Banach space, the eigenvalues need to be replaced with the elements of the spectrum of the operator, i.e. the values $\backslash lambda$ for which $A\; -\; \backslash lambda\; I$ is not bijective. We denote the spectrum by

$\backslash sigma(A)\; =\; \backslash left\backslash \{\; \backslash lambda\; \backslash in\; \backslash Complex:\; A\; -\; \backslash lambda\; I\; \backslash ;\; \backslash text\{is\; not\; bijective\}\; \backslash right\backslash \}$

The spectral radius is then defined as the supremum of the magnitudes of the elements of the spectrum:

$\backslash rho(A)\; =\; \backslash sup\_\{\backslash lambda\; \backslash in\; \backslash sigma(A)\}\; |\backslash lambda|$

Gelfand's formula, also known as the spectral radius formula, also holds for bounded linear operators: letting $\backslash |\backslash cdot\backslash |$ denote the operator norm, we have

$\backslash rho(A)\; =\; \backslash lim\_\{k\; \backslash to\; \backslash infty\}\backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}=\backslash inf\_\{k\backslash in\backslash mathbb\{N\}^*\}\; \backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}.$

A bounded operator (on a complex Hilbert space) is called a spectraloid operator if its spectral radius coincides with its numerical radius. An example of such an operator is a normal operator.

---

Graphs The spectral radius of a finite graph is defined to be the spectral radius of its adjacency matrix.

This definition extends to the case of infinite graphs with bounded degrees of vertices (i.e. there exists some real number such that the degree of every vertex of the graph is smaller than ). In this case, for the graph define:

Let be the adjacency operator of :

$\backslash begin\{cases\}\; \backslash gamma\; :\; \backslash ell^2(G)\; \backslash to\; \backslash ell^2(G)\; \backslash \backslash \; (\backslash gamma\; f)(v)\; =\; \backslash sum\_\{(u,v)\; \backslash in\; E(G)\}\; f(u)\; \backslash end\{cases\}$

The spectral radius of is defined to be the spectral radius of the bounded linear operator .

---

Upper bounds

---

Upper bounds on the spectral radius of a matrix The following proposition gives simple yet useful upper bounds on the spectral radius of a matrix.

Proposition. Let with spectral radius and a sub-multiplicative matrix norm . Then for each integer $k\; \backslash geqslant\; 1$:

:$\backslash rho(A)\backslash leq\; \backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}.$

Proof

Let be an eigenvector-eigenvalue pair for a matrix A. By the sub-multiplicativity of the matrix norm, we get:

$|\backslash lambda|^k\backslash |\backslash mathbf\{v\}\backslash |\; =\; \backslash |\backslash lambda^k\; \backslash mathbf\{v\}\backslash |\; =\; \backslash |A^k\; \backslash mathbf\{v\}\backslash |\; \backslash leq\; \backslash |A^k\backslash |\backslash cdot\backslash |\backslash mathbf\{v\}\backslash |.$

Since , we have

$|\backslash lambda|^k\; \backslash leq\; \backslash |A^k\backslash |$

and therefore

$\backslash rho(A)\backslash leq\; \backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}.$

concluding the proof.

---

Upper bounds for spectral radius of a graph There are many upper bounds for the spectral radius of a graph in terms of its number n of vertices and its number m of edges. For instance, if

$\backslash frac\{(k-2)(k-3)\}\{2\}\; \backslash leq\; m-n\; \backslash leq\; \backslash frac\{k(k-3)\}\{2\}$

where $3\; \backslash le\; k\; \backslash le\; n$ is an integer, then

$\backslash rho(G)\; \backslash leq\; \backslash sqrt\{2\; m-n-k+\backslash frac\{5\}\{2\}+\backslash sqrt\{2\; m-2\; n+\backslash frac\{9\}\{4\}\}\}$

---

Symmetric matrices For real-valued matrices $A$ the inequality $\backslash rho(A)\; \backslash leq\; \{\backslash |A\backslash |\}\_\{2\}$ holds in particular, where $\{\backslash |\backslash cdot\backslash |\}\_\{2\}$ denotes the spectral norm. In the case where $A$ is symmetric, this inequality is tight:

Theorem. Let $A\; \backslash in\; \backslash mathbb\{R\}^\{n\; \backslash times\; n\}$ be symmetric, i.e., $A\; =\; A^T.$ Then it holds that $\backslash rho(A)\; =\; \{\backslash |A\backslash |\}\_\{2\}.$

Proof

Let $(v\_i,\; \backslash lambda\_i)\_\{i=1\}^\{n\}$ be the eigenpairs of A. Due to the symmetry of A, all $v\_i$ and $\backslash lambda\_i$ are real-valued and the eigenvectors $v\_i$ are orthonormal. By the definition of the spectral norm, there exists an $x\; \backslash in\; \backslash mathbb\{R\}^\{n\}$ with $\{\backslash |x\backslash |\}\_\{2\}\; =\; 1$ such that $\{\backslash |A\backslash |\}\_\{2\}\; =\; \{\backslash |\; A\; x\; \backslash |\}\_\{2\}.$ Since the eigenvectors $v\_i$ form a basis of $\backslash mathbb\{R\}^\{n\},$ there exists factors $\backslash delta\_\{1\},\; \backslash ldots,\; \backslash delta\_\{n\}\; \backslash in\; \backslash mathbb\{R\}^\{n\}$ such that $\backslash textstyle\; x\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; v\_\{i\}$ which implies that

$A\; x\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\backslash delta\_\{i\}\; A\; v\_\{i\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; \backslash lambda\_\{i\}\; v\_\{i\}.$

From the orthonormality of the eigenvectors $v\_i$ it follows that

$\{\backslash |\; A\; x\backslash |\}\_\{2\}\; =\; \backslash |\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; \backslash lambda\_\{i\}\; v\_\{i\}\backslash |\_\{2\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}$ \cdot \cdot {\| v_{i}\|}_{2} = \sum_{i = 1}^{n} \cdot

and

$\{\backslash |x\backslash |\}\_\{2\}\; =\; \backslash |\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; v\_\{i\}\; \backslash |\_\{2\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}$ \cdot {\| v_{i} \|}_{2} = \sum_{i = 1}^{n} .

Since $x$ is chosen such that it maximizes $\{\backslash |Ax\backslash |\}\_\{2\}$ while satisfying $\{\backslash |x\backslash |\}\_\{2\}\; =\; 1,$ the values of $\backslash delta\_\{i\}$ must be such that they maximize $\backslash textstyle\; \backslash sum\_\{i\; =\; 1\}^\{n\}$

\cdot while satisfying $\backslash textstyle\; \backslash sum\_\{i\; =\; 1\}^\{n\}$ = 1. This is achieved by setting $\backslash delta\_\{k\}\; =\; 1$ for $k\; =\; \backslash mathrm\{arg\backslash ,max\}\_\{i=1\}^\{n\}$ and $\backslash delta\_\{i\}\; =\; 0$ otherwise, yielding a value of $\{\backslash |Ax\backslash |\}\_\{2\}\; =$ = \rho(A).

---

Power sequence The spectral radius is closely related to the behavior of the convergence of the power sequence of a matrix; namely as shown by the following theorem.

Theorem. Let with spectral radius . Then if and only if

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; A^k\; =\; 0.$

On the other hand, if , $\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash |A^k\backslash |\; =\; \backslash infty$. The statement holds for any choice of matrix norm on .

Proof

Assume that $A^k$ goes to zero as $k$ goes to infinity. We will show that . Let be an eigenvector-eigenvalue pair for A. Since , we have

$\backslash begin\{align\}$

 0 &= \left(\lim_{k \to \infty} A^k \right) \mathbf{v} \\
   &= \lim_{k \to \infty} \left(A^k\mathbf{v} \right ) \\
   &= \lim_{k \to \infty} \lambda^k\mathbf{v} \\
   &= \mathbf{v} \lim_{k \to \infty} \lambda^k
     

\end{align}

Since by hypothesis, we must have

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\backslash lambda^k\; =\; 0,$

which implies . Since this must be true for any eigenvalue $\backslash lambda$, we can conclude that .

Now, assume the radius of is less than . From the Jordan normal form theorem, we know that for all , there exist with non-singular and block diagonal such that:

$A\; =\; VJV^\{-1\}$

with

$J=\backslash begin\{bmatrix\}$

J_{m_1}(\lambda_1) & 0 & 0 & \cdots & 0 \\ 0 & J_{m_2}(\lambda_2) & 0 & \cdots & 0 \\ \vdots & \cdots & \ddots & \cdots & \vdots \\ 0 & \cdots & 0 & J_{m_{s-1}}(\lambda_{s-1}) & 0 \\ 0 & \cdots & \cdots & 0 & J_{m_s}(\lambda_s) \end{bmatrix}

where

$J\_\{m\_i\}(\backslash lambda\_i)=\backslash begin\{bmatrix\}$

\lambda_i & 1 & 0 & \cdots & 0 \\ 0 & \lambda_i & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_i & 1 \\ 0 & 0 & \cdots & 0 & \lambda_i \end{bmatrix}\in \mathbf{C}^{m_i \times m_i}, 1\leq i\leq s.

It is easy to see that

$A^k=VJ^kV^\{-1\}$

and, since is block-diagonal,

$J^k=\backslash begin\{bmatrix\}$

J_{m_1}^k(\lambda_1) & 0 & 0 & \cdots & 0 \\ 0 & J_{m_2}^k(\lambda_2) & 0 & \cdots & 0 \\ \vdots & \cdots & \ddots & \cdots & \vdots \\ 0 & \cdots & 0 & J_{m_{s-1}}^k(\lambda_{s-1}) & 0 \\ 0 & \cdots & \cdots & 0 & J_{m_s}^k(\lambda_s) \end{bmatrix}

Now, a standard result on the -power of an $m\_i\; \backslash times\; m\_i$ Jordan block states that, for $k\; \backslash geq\; m\_i-1$:

$J\_\{m\_i\}^k(\backslash lambda\_i)=\backslash begin\{bmatrix\}$

\lambda_i^k & {k \choose 1}\lambda_i^{k-1} & {k \choose 2}\lambda_i^{k-2} & \cdots & {k \choose m_i-1}\lambda_i^{k-m_i+1} \\ 0 & \lambda_i^k & {k \choose 1}\lambda_i^{k-1} & \cdots & {k \choose m_i-2}\lambda_i^{k-m_i+2} \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_i^k & {k \choose 1}\lambda_i^{k-1} \\ 0 & 0 & \cdots & 0 & \lambda_i^k \end{bmatrix}

Thus, if then for all . Hence for all we have:

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}J\_\{m\_i\}^k=0$

which implies

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; J^k\; =\; 0.$

Therefore,

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}A^k=\backslash lim\_\{k\; \backslash to\; \backslash infty\}VJ^kV^\{-1\}=V\; \backslash left\; (\backslash lim\_\{k\; \backslash to\; \backslash infty\}J^k\; \backslash right\; )V^\{-1\}=0$

On the other side, if $\backslash rho(A)>1$, there is at least one element in that does not remain bounded as increases, thereby proving the second part of the statement.

---

Gelfand's formula Gelfand's formula, named after Israel Gelfand, gives the spectral radius as a limit of matrix norms.

---

Theorem For any matrix norm we haveThe formula holds for any Banach algebra; see Lemma IX.1.8 in and

$\backslash rho(A)=\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}$.

Moreover, in the case of a matrix norm matrix norm $\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}$ approaches $\backslash rho(A)$ from above (indeed, in that case $\backslash rho(A)\; \backslash leq\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}$ for all $k$).

---

Proof For any , let us define the two following matrices:

$A\_\{\backslash pm\}=\; \backslash frac\{1\}\{\backslash rho(A)\; \backslash pm\backslash varepsilon\}A.$

Thus,

We start by applying the previous theorem on limits of power sequences to :

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; A\_+^k=0.$

This shows the existence of such that, for all ,

Therefore,

Similarly, the theorem on power sequences implies that $\backslash |A\_-^k\backslash |$ is not bounded and that there exists such that, for all ,

$\backslash left\backslash |A\_-^k\; \backslash right\; \backslash |\; >\; 1.$

Therefore,

$\backslash left\backslash |A^k\; \backslash right\backslash |^\{\backslash frac\{1\}\{k\}\}\; >\; \backslash rho(A)-\backslash varepsilon.$

Let }. Then,

that is,

$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}\; =\; \backslash rho(A).$

This concludes the proof.

---

Corollary Gelfand's formula yields a bound on the spectral radius of a product of commuting matrices: if $A\_1,\; \backslash ldots,\; A\_n$ are matrices that all commute, then

$\backslash rho(A\_1\; \backslash cdots\; A\_n)\; \backslash leq\; \backslash rho(A\_1)\; \backslash cdots\; \backslash rho(A\_n).$

---

Numerical example Consider the matrix

$A=\backslash begin\{bmatrix\}$

9 & -1 & 2\\ -2 & 8 & 4\\ 1 & 1 & 8 \end{bmatrix}

whose eigenvalues are ; by definition, . In the following table, the values of $\backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}$ for the four most used norms are listed versus several increasing values of k (note that, due to the particular form of this matrix,$\backslash |.\backslash |\_1=\backslash |.\backslash |\_\backslash infty$):

---

Notes and references

---

Bibliography

---

See also

• Power iteration
• Spectral gap
• The Joint spectral radius is a generalization of the spectral radius to sets of matrices.
• Spectrum of a matrix
• Spectral abscissa

Post Comment